SuperHack/SuperHack CD.bin/CODING/GRAPHICS/VGATUT2.ZIP/TUT2.TXT

Text File | 1995-08-12 | 19.5 KB | 549 lines

            ╒═════════════════════════╕
            │░░░▓░░░▓░░░▓▓▓░░░░░▓░░░░░│
            │░░░▓░░░▓░░▓░░░░░░░▓░▓░░░░│
            │░░░░▓░▓░░░▓░░▓▓░░▓░░░▓░░░│
            │░░░░▓░▓░░░▓░░░▓░░▓▓▓▓▓░░░│
            │░░░░░▓░░░░░▓▓▓░░░▓░░░▓░░░│
            ├═════════════════════════┤
            │Part II - LINES & CIRCLES│
            └─────────────────────────┘

Hi and welcome to the issue number 2 of my (ermm.. a bit late) weekly tutorial
on programming graphics for the PC.

Firstly, *many* thanks to Richard Griffiths for porting the code in this
tutorial to Pascal.

This tutorial is about lines, circles & how to draw them.

Before we start :

═══════════════════════════════════════════════════════════════════════════════
┌══════════╗
│DISCLAIMER║
└──────────╜
    The code for this tutorial, the compiled .EXEs and any ascociated text
    are freely distributable on the conditions that the contents of the
    original .ZIP file are distributed as one and that no changes are made
    to any of the data or information contained within.
    The author expresses no warranty implied or otherwise as to the
    suitabilty of this software for execution on any machine other than
    the system on which it was developed (although there should be no
    problems).
    The author also takes no responsibilty for damage resulting from the
    use of information, code or otherwise, obtained from this tutorial
    (again, I'd be surprised if such a thing did happen).
    Finally you should _NOT_ have paid anything for this tutorial.
    If you parted with any money (other than a reasonalbe price for a
    disk) then complain and get your money back.  Please let me know too.
    This tutorial is FREE.  Please do not abuse this.
═══════════════════════════════════════════════════════════════════════════════

Sorry about all that, but unfortunately we live in a world where such things
are a necessity.

Time is short, so lets press on.......

Drawing a line.  What could be simpler?  Well, actually lots of things.  Like
riding a bike, brushing your teeth, walking the dog..... no, seriously though
 - the problems involved with drawing a line on a VGA screen are not trivial.

LINES (a brief revision)
────────────────────────

We can describe a line in several ways.  Look at the following....

    y = mx + c

Familliar?  You bet!  This is a standard equation for a line which you should
have learned in maths at school.  What it basically says is, Y is equal to X
multiplied by the gradient of the line (m) plus the Y-intercept (the value of
Y when X = 0, or effectively where it crosses the Y axis).

If we know the gradient of the line, and the point at which it crosses the Y
axis, then we can draw a line of infinate length which fits the equation.
All we need to do is start with X=0 (or -100, or 56.73, or 999, you get the
idea) and using that equation, we can calculate the value of the corresponding
Y coordinate.

How do we find the gradient of the line?
────────────────────────────────────────

The following formula requires us to know at least two points on the line,
which we can then use to calculate the gradient.

    m = (x2-x1)/(y2-y1)

    The points (100,200) & (56, 37) (using the above formula) would give us
    a gradient of 0.27.

    This means that for every change of 1 unit in the X direction, there is a
    change of 0.27 units in the Y direction.  So the first few points of our
    line would look like this.... (assuming a Y intercept of 0)

    X │ Y
    ──┼─────
    0 │ 0
    1 │ 0.27
    2 │ 0.54
    3 │ 0.81
    4 │ 1.08

    As those of you who were paying attention last time will know, we cannot
    plot fractions on the screen and therefore, this approach will need quite
    a bit of change.

What exactly do we want to do?
──────────────────────────────

Instead of using that formula we will write a function which takes the
start and end points of the line and draws the pixels in between.

If you look at a line on a monitor screen, you will see that it is far from
being a perfect line.  It looks more like this....

        OOOOO
             OOOOO
              OOOOO
                   OOOOO

The distance and the overall gradient of this line are as expected, but
because of the fact that we do not have the freedom to play with fractions of
pixels, we must approximate each calculation to the nearest pixel.

How do we do this?

Firstly we need to ensure that the point with the highest value (ie. further
down the screen) appears as X2.  Rather than rely on the parameters being
passed in this order, which limits our function greatly, we will swap them
around if necessary...

    if (X2<X1)
    {
    int Tmp = X2;
    X2 = X1;
    X1 = Tmp;

    Tmp = Y2;
    Y2 = Y1;
    Y1 = Tmp;
    }

Good.  Now the coordinates are in the right order.

The next thing we need to know is weather we a drawing a horizontal or
verticle line.  These two types of line are the simplest to deal with,
because only one value is changed.  If the line is horizontal the gradient
is zero (no change in Y) and if it is vertical, them the gradient is infinate
(an infinite number of Y values for 1 value of X).  So we make sure that we
deal with these two types of line differently.

       if(Y2 != Y1) &&
     (X2 != X1)
       )

Once we have determined that we are drawing a sloped line we have to
calculate the gradient.

    Slope = (float)(Y2-Y1)/(X2-X1); // gradient of line

Now all that we need to do is begin at the first point (X1, Y1) and
step along the line from X1 to X2 with the following loop....

        for (int Temp=X1; Temp<=X2; Temp++)
        {
        PutPixel( Temp, (int)YPos, Colour );
        YPos += Slope;
        }

Here we are adding the value of Slope to the old Y coordination and plotting
the point.  Note that the value of YPos is still a floating point value and
we are 'kludging' the value to an integer by passing it as a variable to a
function which requires an integer value, effectively stripping the decimal
portion from the number (ie. 10.1231 becomes 10)

This mini-function will work fine for lines where the slope is greater than
0 and less than 1.  After that point we begin to have problems....

What happens is that when slope is greater than 1, we are adding too much
to the value of Y, so the line begins to break up.

To deal with this, we split the calculation into two pieces.  The first for
lines of slope less than 1, and well.. the other one... obviously.

So the line drawing looks like this :

    if (Slope<1)
    {
        YPos = Y1;

        for (int Temp=X1; Temp<=X2; Temp++)
        {
        PutPixel( Temp, (int)YPos, Colour );
        YPos += Slope;
        }
    }
    else
    {
        XPos = X1;

        for (int Temp=Y1; Temp<=Y2; Temp++)
        {
        PutPixel( (int)XPos, Temp, Colour );
        XPos += (1/Slope);
        }
    }
    }

Now all that's left is to deal with horizontal or verticle lines...

    else   // from the line - if (Y2 != Y1) &&
    {
    if (X1 == X2)   // verticle
    {
        for (int Temp=Y1; Temp<=Y2; Temp++)
        PutPixel( X1, Temp, Colour );
    }
    else    // horizontal
    {
        for (int Temp=X1; Temp<=X2; Temp++)
        PutPixel( Temp, Y1, Colour );
    }
    }

And there we have it!  The full routine is included with this text.

Slow isn't it?  Using floating point arithmetic is always a killer when
trying to write fast routines.  What we need to do is remove all the
floating point.  Also the repeated calling of the PutPixel function slows
things down a great deal, so we need another *new* way of putting a pixel on
screen.

As it's the gradient which requires the use of floating point math, we
need a way of drawing the line without the need for calculating a gradient.
Fortunately for us, this problem was solved a long time ago by a chap by
the name of Bresenham.  His famous algorithm for drawing lines is very fast
and used widely in many line routines.

The first thing that we need to do is calculate the range of the line.  That
is, the difference between the starting and the ending coordinates.

    XScope = (X2 - X1);
    YScope = (Y2 - Y1);

The values XScope & YScope could easily end up negative and we must have them
positive so we do the following....

    if (XScope < 0)
    {
    XScope =- XScope;   // get absolute value of X term
    XDir = -1;          // direction of line
    }
    else XDir = 1;          // positive

    if (YScope < 0)
    {
    YScope =- YScope;   // get absoulte value of Y term
    YDir = -320;        // familiar?
    }
    else YDir = 320;

As you will remember from the previous tutorial, we declared a variable
which was used to point at video memory.  This variable is a pointer which
we can also treat as an array of 64000 unsigned chars, and when we place a
value in this array it appears on screen.

Therefore the statement :               vga[0] = 15
will place a white pixel at (0,0)

This is the method that we will use in our line routine to avoid having to
call the Setpixel function repeatedly.

    Offset = X1 + (Y1*320); // video offset of first point

That's the stage set, now for the interesting bit....

    LinearDeviance = 0;

This variable is the mainstay of the whole function.  The first thing we do is
(as in the previous function), work out which way the line is running.

    if (XScope > YScope)

We then set the length of the line equal based on the success of the IF test.

    Length = XScope+1;  // success
    Length = YScope+1;  // fail

This means, obviously, that the length that the line is calculated over is
equal to the greater of the two differences.

We then begin our line drawing loop...

    for (int Tmp=0; Tmp <= Length; Tmp++)
    {
        vga[Offset] = Colour;       // put pixel

        LinearDeviance += YScope;

        if (LinearDeviance >= XScope)    // error threshold has been exceeded
        {
        LinearDeviance -= XScope;
        Offset += YDir;
        }

        Offset += XDir;
    }

Here we step though each point on the line, repeatedly adding YScope to
LinearDeviance.  When the deviance of the line (that is the difference between
the pixelated line & the mathematically desired line) becomes greater than
XScope, we subtract XScope and adjust our Y coordinate appropriately.


Now all that's left to do is deal with YScope being greater than XScope...

    {
    Length = YScope+1;

    for (int Tmp=0; Tmp <= Length; Tmp++)
    {
        vga[Offset] = Colour;       // put pixel

        LinearDeviance += XScope;

        if (LinearDeviance >= YScope)    // error threshold has been exceeded
        {
        LinearDeviance -= YScope;
        Offset += XDir;
        }

        Offset += YDir;
    }
    }

And that's it!  Apologies for not delving into this as deeply as I would have
liked but that old swinger 'Father Time' has gotten ahead of me again & I
still have to cover circles....  so let's press on.

By the way, both of these techniques are demonstrated in the programs
accompanying this tutorial.

──────────────────────────────────────────────────────────────────────────────
THE CIRCLE
──────────

We're all familiar with the good old circle.  It is described by three
values : the coordinates of the centre point & the radius.

What we need is a way of generating a circle based on these values.

The function declaration will look like this :

    DrawCircle( int X, int Y, int Radius )


Drawing a Circle
────────────────

In order to draw a circle we must be able to generate integer X & Y
coordinates for each point on the circumference.  The same problems that we
have with drawing a line with integer values also occur when drawing a circle,
only more seriously....

A circle can be described with the following equations....

    X = Cos(Θ)
    Y = Sin(Θ)

Which is great because it provides the data in the exact format that we want,
a coordinate pair.

It is therefore a simple matter to place this, and the PutPixel function
inside a loop which moves through theta (Θ) from 0 to 360 generating the
circle.

Simple!  No.  :(

There are a few things that we must do before this will produce the circle
that we need.

Firstly : The circle will be generated with a radius of 1, at location (0,0),
      which is not in keeping with the specification that we designed
      earlier.

Secondly : The Sin & Cos functions provided by C++ compilers, deal with
       radians, rather than degrees, so we must first tailor our loop to
       deal with this.

Ok.  Moving swiftly onward, we can see that there are some transformations we
can do on our X, Y values to produce the required circle.

We must scale the original circle by the radius, and move it to the desired
location.  Like this....

       PointX = (Cos(Θ) * Radius) + X;  // X is the X coodinate of the centre
       PointY = (Sin(Θ) * Radius) + Y;

This will move our circle from (0,0) to the correct place & scale it to the
appropriate radius at the same time.

Now we plot the point with our PutPixel.

And that's the first problem sorted.

As far as the second problem is concerned, all we need to do is create a loop
like this:

    for (float Tmp=0; Tmp<6.3; Tmp += 0.005)


6.283 radians = 360 degrees

We increment Tmp by 0.005 each loop in order to hit a reasonable sample of
angles.  This is probably a bit overkill (31500 samples) but we'll deal with
that later on.  For now, realise that by increasing this value we speed the
routine up, but also reduce the quality of the circle.

And that's it.  A simple circle drawing routine.

A word of warning.  It's rubbish.  Don't use it. <grin>
When the circles are small they look more like sqaures & when they increase
in size they have holes in them (need to increase sample rate).
Also the function is terribly slow.

A Better Routine
────────────────

There are a number of things that we can do to improve the previous routine.

Ideally, we need to remove the use floating point numbers, as we did for the
line routine (above), but this is not very easy when dealing with Sine &
Cosine functions as they will return floating point values.  I'll work on it
and let you know if I come up with anything better.

The best method of improving the accuracy of the circle is to modify the
sample rate based on the size.  We need a sample rate which provides enough
samples to hit all the pixels required, but not too many so as to slow the
routine down unnecesarily.  I've used the following formula :

    Sample = 1/Radius

This is simply an inverse function which provides a higher sample rate for
larger circles and reduces it for small circles.

Ok.  That's accuracy dealt with.... now for the speed.

I'm tempted to do this in assembly, but I'll stick with C++ code for this
tutorial for simplicity's sake.

Again, rather than use the PutPixel function, I'll use the vga[] array which
we used before, but this time we need to calculate the offset each time rather
than incrementing.  Consider the formula :  (Y*320)+X

By using the SHL operator in assembly code, we managed to speed our PutPixel,
we can use the same trick from C++ code too....

    vga[ (Y<<6)+(Y<<8)+X ] = Colour

The Shift left operator '<<' is used to perform the same operation as the
SHL assembly command.

Now... one last trick.  We will make use of the circle's most obvious
feature.... it's symmetry.

For each point on the circle that we calculate we can mirror it at several
points around the circle.  As the circle has infinate lines of symettry, we
can also have an infinate number of copies (although this is silly) of each
calculated pixel.

We will deal with 2 lines of symetry (you may have guessed, but I don't know
how to spell symettry), meaning that for every point we calculate we repeat
this point at 3 other places around the circle.  This cuts the number of
calculations required to 1/4 of the number used in the previous function! :)

A slight change to the equations for calculating the points are required
here.  We must remove the +X & +Y that we use to position the circle and add
them later on.  They now look like this.....


       PointX = (Cos(Θ) * Radius);
       PointY = (Sin(Θ) * Radius);

We repeat the point like this......

    NewX1 = NewX + X;         // calculated point + transformation
    NewY1 = NewY + Y;

    NewX2 = (NewX * -1) + X;
    NewY2 = (NewY * -1) + Y;

    NewX3 = (NewX * -1) + X;
    NewY3 =  NewY + Y;

    NewX4 =  NewX + X;
    NewY4 = (NewY * -1) + Y;

    screen[( (NewY1<<8) + (NewY1<<6) + NewX1 )] = Colour;
    screen[( (NewY2<<8) + (NewY2<<6) + NewX2 )] = Colour;
    screen[( (NewY3<<8) + (NewY3<<6) + NewX3 )] = Colour;
    screen[( (NewY4<<8) + (NewY4<<6) + NewX4 )] = Colour;

We calculate X & Y using the equations derived earlier and apply
transformations that allow us to position them in the correct places.

This technique can be extended to do 4 lines of reflection (8 repetitions) or
even more, though this introduces floating point calculations & perhaps undo
the advantages.  I'll leave you to experiment.

Goodbye....
───────────

You'll notice that there are a number of source files included with this
Tut.  VGAFUNC.CPP & VGAFUNC.H are my attempt to keep all the best routines
that we could use again, in a single place which can be compiled along with
any new code and save us rewriting ancient routines, over & over again.
At the end of each tutorial then it would be a prudent move to copy the
routines that you like from the original source and move them to this file.
Note that the crappy routines from this Tut are also in this file, and don't
want to be so move them to another file if you want to keep them (heaven
knows why would want to do that?!!)

Next week I'll be looking at the VGA Palette and I'll be providing several
routines to help you do nice things with colours.  I've actually written the
code already, but not the text so you'll have to wait until I have time for
that. ;)

(Standard bit ripped from last tutorial)──────────┐
┌─────────────────────────────────────────────────┴─────────────────────────┐
│If there is anything in this tutorial which you would like further details │
│on, then please do not hesitate to contact me.                             │
│                                                                           │
│If you produce anything nice, then please send it to me.  I am always keen │
│to see other people's work.                                                │
│                                                                           │
│Comments on this tutorial will be gratefully recieved.  Was it any use to  │
│you? Too informal?  Too complicated?  Not clear enough?  Too simple?       │
│What subjects would you like to see covered in later editions?             │
└───────────────────────────────────────────────────────────────────────────┘
┌────┤From 'The Wall' by Pink Floyd├────────────────────────────────────────┐
│                                                                           │
│'Did you see the frightened ones?                                          │
│ Did you hear the falling bombs?                                           │
│ Did you ever wonder why we had to run for shelter,                        │
│ with the promise of a brave new world,                                    │
│ unfurled beneath a clear blue sky?                                        │
│'                                                                          │
└───────────────────────────────────────────────────────────────────────────┘

Barny Mercer    - (original code & text file) 5/8/95 @ 9:25pm

email : [e-mail]
WWW   : http://www.zetnet.co.uk/users/bmercer/
voice : 01595 692097

Richard Griffiths       - Pascal conversion
email : [e-mail]
WWW   : http://www.zetnet.co.uk/users/rgriff/